#include<iostream>
using namespace std;

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
bool check(TreeNode *o, TreeNode *t) {
        if (!o && !t) {
            return true;
        }
        if ((o && !t) || (!o && t) || (o->val != t->val)) {
            return false;
        }
        return check(o->left, t->left) && check(o->right, t->right);
    }

    bool dfs(TreeNode *o, TreeNode *t) {
        if (!o) {
            return false;
        }
        return check(o, t) || dfs(o->left, t) || dfs(o->right, t);
    }

    bool isSubtree(TreeNode *s, TreeNode *t) {
        return dfs(s, t);
    }
int main()
{
    TreeNode* rootNode = new TreeNode(0);
    TreeNode* subRootNode = new TreeNode(0);
    TreeNode* cur1 = rootNode;
    TreeNode* cur2 = subRootNode;
    cout<<"Enter the root node value: ";
    for(int i=0;i<=1;i++)
    {
        cin>>cur1->val;
        TreeNode* left = new TreeNode(0);
        TreeNode* right = new TreeNode(0);
        cin>>left->val;
        cin>>right->val;
        cur1->left = left;
        cur1->right = right;
        cur1 = cur1->left;
    }
    cout<<"Enter the sub root node value: ";
    for(int i=0;i<=0;i++)
    {
        cin>>cur2->val;
        TreeNode* left = new TreeNode(0);
        TreeNode* right = new TreeNode(0);
        cin>>left->val;
        cin>>right->val;
        cur2->left = left;
        cur2->right = right;
        cur2 = cur2->left;
    }
    isSubtree(rootNode, subRootNode) ? cout<<"true":cout<<"false";
    return 0;
}
